Эквивалентность минимальности, индуктивности и обрыва

Отношение порядка $\preceq$ на множестве $A$ удовлетворяет **условию минимальности**, если для любого непустого подмножества $B \subseteq A$ в частично упорядоченном множестве $(B, \preceq|_B)$ есть минимальный элемент.

Отношение порядка $\preceq$ на множестве $A$ удовлетворяет **условию индуктивности**, если любое свойство $P(a)$ элементов множества $A$ такое, что: * $P(a)$ для любого минимального элемента $a$ (база) * Если $P(b)$ для любого элемента $b$ такого, что $b \prec a$, то $P(a)$ (шаг) выполнено для всех элементов $A$.

Отношение порядка $\preceq$ на множестве $A$ удовлетворяет **условию обрыва убывающих цепей**, если любая убывающая последовательность элементов $A$ (цепь) с условием $\dots \prec a_n \prec \dots \prec a_2 \prec a_1$ конечна.

Условия минимальности, индуктивности и обрыва убывающих цепей эквивалентны.

**Минимальность $\implies$ индуктивность (от противного)** Пусть $P$ — свойство, для которого не выполняется индуктивность, т.е. выполнены база и шаг индукции, но есть хотя бы один элемент такой, что $\neg P(a)$ Пусть $B = \{a \mid \neg P(a)\}$; в $B$ есть минимальный элемент, назовем его $b$ $b$ не минимален в $A$, потому что $\neg P(b)$ противоречит базе Значит $P(a)$ для всех $a < b$, и $\neg P(b)$ противоречит шагу. **Индуктивность $\implies$ обрыв убывающих цепей (по индукции)** Пусть $P(a)$ означает, что все убывающие цепи, такие что $a_1 = a$, конечны. Для минимального $a$ цепь одна и состоит из $a$ — **база выполнена** Если для всех элементов, меньших $a$, цепи конечны, то $a$ увеличивает длину каждой из таких цепей на 1, т.е. цепи, начинающиеся с $a$, тоже конечны — **шаг выполнен** Значит по индукции $P(a)$ выполнено для всех $a$, а это и есть условие обрыва **Обрыв убывающих цепей $\implies$ минимальность (в лоб)** Найдем минимальный элемент в произвольном непустом $B \subseteq A$ Возьмем произвольный $a_1 \in B$; если он минимальный — OK Иначе существует $a_2 \in B$ такой, что $a_2 < a_1$; если он минимальный — OK Иначе существует $a_3 \in B$ такой, что $a_3 < a_2 < a_1$ ... Процесс будет конечным, так как бесконечных убывающих цепей нет Значит минимальный элемент будет найден за конечное число шагов $\square$